/*
 * @lc app=leetcode.cn id=787 lang=cpp
 *
 * [787] K 站中转内最便宜的航班
 */
#include "include.h"
// @lc code=start
class SolutionBellmanFord {
public:
    // todo : Bellman Ford
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        std::vector<int> dist(n, INF);
        dist[src] = 0;
        for (int limit = 0; limit < k + 1; limit++) {
            std::vector<int> clone = dist;
            for (auto& f : flights) {
                int x = f[0], y = f[1], w = f[2];
                dist[y] = std::min(dist[y], clone[x] + w);
            }
        }
        return dist[dst] > INF / 2 ? -1 : dist[dst];
    }
private:
    int N = 110, INF = 0x3f3f3f3f;
};

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {

        // djkstra has no jump time limit ...
        // 解决有边数限制的最短路问题 :
        // Bellman Ford/SPFA 都是基于动态规划，其原始的状态定义为 f[i][k]
        // f[i][k] 代表从起点到 ii 点，且经过最多 kk 条边的最短路径。
        // 同样多源汇最短路算法 Floyd 也是基于动态规划，其原始的三维状态定义为 f[i][j][k]
        // f[i][j][k] 代表从点 ii 到点 jj，且经过的所有点编号不会超过 kk（即可使用点编号范围为 [1, k][1,k]）的最短路径。
        // 使用 Floyd 求最小环或者求“重心点”（即删除该点后，最短路值会变大）。

        // 求解最短路一般有三种方法，floyd算法，dijkstra算法和bellman ford算法。
        // 这题使用bellman ford算法是适用性最强的，因为该算法的第k步就是求出的从给定起点到所有节点经过最多k步的最短路。

        // use n * (k+1) array to cache 0~k jump min cost
        minCostDP.resize(n, std::vector<int>(k+1, INT32_MAX));
        minCostDP[src][0] = 0;

        // init src => neighbors
        for (auto& flight : flights){
            int from = flight[0];
            int to = flight[1];
            int fee = flight[2];
            
            if (from == src){
                minCostDP[to][0] = fee;
            }
        }

        // !!!!!!!!!!!!!!!!!!!!!!
        // traverse by jump times, not by nodeFrom to nodeTo
        for (int i=1;i<k+1;++i){
            for (auto& flight : flights){
                int from = flight[0];
                int to = flight[1];
                int fee = flight[2];

                if (minCostDP[from][i-1] == INT32_MAX){continue;}
                
                if (minCostDP[from][i-1] + fee < minCostDP[to][i]){
                    minCostDP[to][i] = minCostDP[from][i-1] + fee;
                }
            }
        }

        int minCost = INT32_MAX;

        for (int i=0;i<k+1;++i){
            if (minCostDP[dst][i] < minCost){minCost = minCostDP[dst][i];}
        }

        return minCost < INT32_MAX ? minCost : -1;
    }
private:
    std::vector<std::vector<int>> minCostDP;
};
// @lc code=end

// 17\n[[0,12,28],[5,6,39],[8,6,59],[13,15,7],[13,12,38],[10,12,35],[15,3,23],[7,11,26],[9,4,65],[10,2,38],[4,7,7],[14,15,31],[2,12,44],[8,10,34],[13,6,29],[5,14,89],[11,16,13],[7,3,46],[10,15,19],[12,4,58],[13,16,11],[16,4,76],[2,0,12],[15,0,22],[16,12,13],[7,1,29],[7,14,100],[16,1,14],[9,6,74],[11,1,73],[2,11,60],[10,11,85],[2,5,49],[3,4,17],[4,9,77],[16,3,47],[15,6,78],[14,1,90],[10,5,95],[1,11,30],[11,0,37],[10,4,86],[0,8,57],[6,14,68],[16,8,3],[13,0,65],[2,13,6],[5,13,5],[8,11,31],[6,10,20],[6,2,33],[9,1,3],[14,9,58],[12,3,19],[11,2,74],[12,14,48],[16,11,100],[3,12,38],[12,13,77],[10,9,99],[15,13,98],[15,12,71],[1,4,28],[7,0,83],[3,5,100],[8,9,14],[15,11,57],[3,6,65],[1,3,45],[14,7,74],[2,10,39],[4,8,73],[13,5,77],[10,0,43],[12,9,92],[8,2,26],[1,7,7],[9,12,10],[13,11,64],[8,13,80],[6,12,74],[9,7,35],[0,15,48],[3,7,87],[16,9,42],[5,16,64],[4,5,65],[15,14,70],[12,0,13],[16,14,52],[3,10,80],[14,11,85],[15,2,77],[4,11,19],[2,7,49],[10,7,78],[14,6,84],[13,7,50],[11,6,75],[5,10,46],[13,8,43],[9,10,49],[7,12,64],[0,10,76],[5,9,77],[8,3,28],[11,9,28],[12,16,87],[12,6,24],[9,15,94],[5,7,77],[4,10,18],[7,2,11],[9,5,41]]\n13\n4\n13

class SolutionViolent {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        // build graph
        // neighbor list

        // <to, cost>
        neighborList.resize(n, std::vector<std::pair<int, int>>());

        for (auto& flight : flights){
            neighborList[flight[0]].emplace_back(flight[1], flight[2]);
        }

        visited.resize(n, 0);

        // dfs + trace back
        // ends when jump = k+1 or reach destination

        visited[src] = 1;
        dfs(src, dst, k);

        return minCost < INT32_MAX ? minCost : -1;
    }
private:
    std::vector<std::vector<std::pair<int, int>>> neighborList;
    std::vector<int> visited;
    int minCost = INT32_MAX;
    int currentCost = 0;
    int jumpFrequency = 0;

    void dfs(int from, int destination, int jumpLimit){
        if (from == destination){
            // reach
            if (currentCost < minCost){minCost = currentCost;}
            return;
        }

        if (jumpFrequency == jumpLimit+1){
            // can not continue jumpping ~
            return;
        }

        for (auto& ticket : neighborList[from]){
            int to = ticket.first;
            int fee = ticket.second;

            visited[to] = 1;
            currentCost += fee;
            jumpFrequency += 1;

            dfs(to, destination, jumpLimit);

            visited[to] = 0;
            currentCost -= fee;
            jumpFrequency -= 1;
        }
    }
};
